package countSort;

import java.util.ArrayList;
import java.util.List;

public class CountSort {

    /**
     * 计数排序 看不懂的话参考countBookSort代码
     * @param list 需要排序的数组
     * @return 返回排序完成的数组
     */
    public static List<Integer> countSort(List<Integer> list){
        //获取最大值最小值 计算出差值
        Integer max = list.get(0);
        Integer min = list.get(0);
        for (Integer integer : list) {
            if (integer > max) max = integer;
            if (integer < min) min = integer;
        }
        int d = max - min;
        //创建数组并开始计数  list是一个动态扩容容器 所以需要如下的操作来初始化一个list
        List<Integer> countList = new ArrayList<>();
        for (int i = 0; i < d + 1; i++) {
            countList.add(0);
        }
        for (int i = 0; i < list.size(); i++) {
            countList.set(list.get(i) - min,countList.get(list.get(i) - min) + 1);
        }
        //计数的数组变形 后面的元素等于前面元素的和
        for (int i = 1; i < countList.size(); i++) {
            countList.set(i, countList.get(i) + countList.get(i - 1));
        }
        //倒叙遍历原数组 并在计数数组中找到正确的位置 输出得到结果
        List<Integer> resourceList = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            resourceList.add(0);
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            //计算位置
            resourceList.set((countList.get(list.get(i) - min) - 1),list.get(i));
            countList.set(list.get(i) - min,countList.get(list.get(i) - min) - 1);
        }
        return resourceList;
    }
}
